<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
    <head>
        <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />

        <meta property="og:title" content="Haskell 趣學指南" />
        <meta property="og:type" content="website" />
        <meta property="og:url" content="http://learnyouahaskell-zh-tw.csie.org" />
        <meta property="og:image" content="http://learnyouahaskell-zh-tw.csie.org/img/bird.png" />

        <style type="text/css">
            @import url(../css/style.css);
            @import url(../css/feedback.css);
        </style>
        <script type="text/javascript" src="../js/jquery.js"></script>
        <script type="text/javascript" src="../js/jquery.chili-2.2.js"></script>
        <script type="text/javascript" src="../js/script.js"></script>
        <script type="text/javascript" src="../js/html2canvas.js"></script>
        <script type="text/javascript" src="../js/jsfeedback.js"></script>
        <script type="text/javascript">
             ChiliBook.recipeFolder = "../js/chili/";  
             ChiliBook.automaticSelector = "pre";
        </script>
        <script type="text/javascript">
            $(function(){
                $('#feedback').click(function(){
                    $('body').feedback();
                })
            });
        </script>
        <script defer type="text/javascript">
            var _gaq = _gaq || [];
            _gaq.push(['_setAccount', 'UA-32830659-1']);
            _gaq.push(['_trackPageview']);

            (function() {
                var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true;
                ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
                    var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s);
            })();
        </script>
        <title>递归</title>
    </head>
    <body>
        <div id="header">
        </div>

        <div id="main">
            <ul class="nav">
                <li class="left">  <img src="../img/prv.png" alt="prev" /><a href="syntax-on-function.html">函数的语法</a></li>
                <li class="center"><a href="chapters.html">目录</a></li>
                <li class="right"> <a href="high-order-function.html">高阶函数</a><img src="../img/nxt.png" alt="next" /></li>
            </ul>
            <a name="递归"></a><h1>递归</h1>

<a name="你好，递归！"></a><h2>你好，递归！</h2>

<img src="../img/recursion.png" alt="" style="float:right" class="floatright" />
<p>前面的章节中我们简要谈了一下递归。而在本章，我们会深入地了解到它为何在 Haskell 中是如此重要，能够以递归思想写出简洁优雅的代码。 </p>

<p>如果你还不知道什么是递归，就读这个句子。哈哈！开个玩笑而已！递归实际上是定义函数以调用自身的方式。在数学定义中，递归随处可见，如斐波那契数列 （fibonacci）。它先是定义两个非递归的数：<code>F(0)=0,F(1)=1</code>，表示斐波那契数列的前两个数为 0 和 1。然后就是对其他自然数，其斐波那契数就是它前面两个数字的和，即 <code>F(N)=F(N-1)+F(N-2)</code>。这样一来，<code>F(3)</code> 就是 <code>F(2)+F(1)</code>，进一步便是 <code>(F(1)+F(0))+F(1)</code>。已经下探到了前面定义的非递归斐波那契数，可以放心地说 <code>F(3)</code> 就是 2 了。在递归定义中声明的一两个非递归的值（如 <code>F(0)</code> 和 <code>F(1)</code>） 也可以称作<b>边界条件</b>，这对递归函数的正确求值至关重要。要是前面没有定义 <code>F(0)</code> 和 <code>F(1)</code> 的话，它下探到 0 之后就会进一步到负数，你就永远都得不到结果了。一不留神它就算到了 <code>F(-2000)=F(-2001)+F(-2002)</code>，并且永远都算不到头！ </p>

<p>递归在 Haskell 中非常重要。命令式语言要求你提供求解的步骤，Haskell 则倾向于让你提供问题的描述。这便是 Haskell 没有 <code>while</code> 或 <code>for</code> 循环的原因，递归是我们的替代方案。</p>
<a name="实作_Maximum"></a><h2>实作 Maximum</h2>


<p><code>maximum</code> 函数取一组可排序的 List（属于 Ord Typeclass） 做参数，并回传其中的最大值。想想，在命令式风格中这一函数该怎么实现。很可能你会设一个变量来存储当前的最大值，然后用循环遍历该 List，若存在比这个值更大的元素，则修改变量为这一元素的值。到最后，变量的值就是运算结果。唔！描述如此简单的算法还颇费了点口舌呢！</p>

<p>现在看看递归的思路是如何：我们先定下一个边界条件，即处理单个元素的 List 时，回传该元素。如果该 List 的头部大于尾部的最大值，我们就可以假定较长的 List 的最大值就是它的头部。而尾部若存在比它更大的元素，它就是尾部的最大值。就这么简单！现在，我们在 Haskell 中实现它</p>
<pre class="code">maximum' :: (Ord a) =&gt; [a] -&gt; a  
maximum' [] = error "maximum of empty list"  
maximum' [x] = x  
maximum' (x:xs)   
    | x &gt; maxTail = x  
    | otherwise = maxTail  
    where maxTail = maximum' xs</pre>
<p>如你所见，模式匹配与递归简直就是天造地设！大多数命令式语言中都没有模式匹配，于是你就得造一堆 if-else 来测试边界条件。而在这里，我们仅需要使用模式将其表示出来。第一个模式说，如果该 List 为空，崩溃！就该这样，一个空 List 的最大值能是啥？我不知道。第二个模式也表示一个边缘条件，它说， 如果这个 List 仅包含单个元素，就回传该元素的值。</p>

<p>现在是第三个模式，执行动作的地方。 通过模式匹配，可以取得一个 List 的头部和尾部。这在使用递归处理 List 时是十分常见的。出于习惯，我们用个 <code>where</code> 语句来表示 <code>maxTail</code> 作为该 List 中尾部的最大值，然后检查头部是否大于尾部的最大值。若是，回传头部；若非，回传尾部的最大值。</p>

<p>我们取个 List <code>[2,5,1]</code> 做例子来看看它的工作原理。当调用 <code>maximum'</code> 处理它时，前两个模式不会被匹配，而第三个模式匹配了它并将其分为 <code>2</code> 与 <code>[5,1]</code>。 <code>where</code> 子句再取 <code>[5,1]</code> 的最大值。于是再次与第三个模式匹配，并将 <code>[5,1]</code> 分割为 <code>5</code> 和 <code>[1]</code>。继续，<code>where</code> 子句取 <code>[1]</code> 的最大值，这时终于到了边缘条件！回传 <code>1</code>。进一步，将 <code>5</code> 与 <code>[1]</code> 中的最大值做比较，易得 <code>5</code>，现在我们就得到了 <code>[5,1]</code> 的最大值。再进一步，将 <code>2</code> 与 <code>[5,1]</code> 中的最大值相比较，可得 <code>5</code> 更大，最终得 <code>5</code>。</p>

<p>改用 <code>max</code> 函数会使代码更加清晰。如果你还记得，<code>max</code> 函数取两个值做参数并回传其中较大的值。如下便是用 <code>max</code> 函数重写的 <code>maximun'</code></p>
<pre class="code">maximum' :: (Ord a) =&gt; [a] -&gt; a  
maximum' [] = error "maximum of empty list"  
maximum' [x] = x  
maximum' (x:xs) = max x (maximum' xs)</pre>
<p>太漂亮了！一个 List 的最大值就是它的首个元素与它尾部中最大值相比较所得的结果，简明扼要。</p>
<img src="../img/maxs.png" alt="" style="float:none" class="floatnone" /><a name="来看几个递归函数"></a><h2>来看几个递归函数</h2>


<p>现在我们已经了解了递归的思路,接下来就使用递归来实现几个函数. 先实现下 <code>replicate</code> 函数, 它取一个 <code>Int</code> 值和一个元素做参数, 回传一个包含多个重复元素的 List, 如 <code>replicate 3 5</code> 回传 <code>[5,5,5]</code>. 考虑一下, 我觉得它的边界条件应该是负数. 如果要 <code>replicate</code> 重复某元素零次, 那就是空 List. 负数也是同样, 不靠谱.</p>
<pre class="code">replicate' :: (Num i, Ord i) =&gt; i -&gt; a -&gt; [a]  
replicate' n x  
    | n &lt;= 0    = []  
    | otherwise = x:replicate' (n-1) x</pre>
<p>在这里我们使用了 guard 而非模式匹配, 是因为这里做的是布林判断. 如果 <code>n</code> 小于 0 就回传一个空 List, 否则, 回传以 <code>x</code> 作首个元素并后接重复 <code>n-1</code> 次 <code>x</code> 的 List. 最后, <code>(n-1)</code> 的那部分就会令函数抵达边缘条件.</p>
<blockquote>
<p><b>Note</b>: Num 不是 Ord 的子集, 表示数字不一定得拘泥于排序, 这就是在做加减法比较时要将 Num 与 Ord 类型约束区别开来的原因.</p>
</blockquote>

<p>接下来实现 <code>take</code> 函数, 它可以从一个 List 取出一定数量的元素. 如 <code>take 3 [5,4,3,2,1]</code>, 得 <code>[5,4,3]</code>. 若要取零或负数个的话就会得到一个空 List. 同样, 若是从一个空 List中取值, 它会得到一个空 List. 注意, 这儿有两个边界条件, 写出来:</p>
<pre class="code">take' :: (Num i, Ord i) =&gt; i -&gt; [a] -&gt; [a]  
take' n _  
    | n &lt;= 0   = []  
take' _ []     = []  
take' n (x:xs) = x : take' (n-1) xs</pre><img src="../img/painter.png" alt="" style="float:right" class="floatright" />
<p>首个模式辨认若为 0 或负数, 回传空 List. 同时注意这里用了一个 guard 却没有指定 <code>otherwise</code> 部分, 这就表示 <code>n</code> 若大于 0, 会转入下一模式. 第二个模式指明了若试图从一个空 List 中取值, 则回传空 List. 第三个模式将 List 分割为头部和尾部, 然后表明从一个 List 中取多个元素等同于令 <code>x</code> 作头部后接从尾部取 <code>n-1</code> 个元素所得的 List. 假如我们要从 <code>[4,3,2,1]</code> 中取 3 个元素, 试着从纸上写出它的推导过程</p>

<p><code>reverse</code> 函数简单地反转一个 List, 动脑筋想一下它的边界条件! 该怎样呢? 想想...是空 List! 空 List 的反转结果还是它自己. Okay, 接下来该怎么办? 好的, 你猜的出来. 若将一个 List 分割为头部与尾部, 那它反转的结果就是反转后的尾部与头部相连所得的 List. </p>
<pre class="code">reverse' :: [a] -&gt; [a]  
reverse' [] = []  
reverse' (x:xs) = reverse' xs ++ [x]</pre>
<p>继续下去!</p>

<p>Haskell 支持无限 List，所以我们的递归就不必添加边界条件。这样一来，它可以对某值计算个没完, 也可以产生一个无限的数据结构，如无限 List。而无限 List 的好处就在于我们可以在任意位置将它断开. </p>

<p><code>repeat</code> 函数取一个元素作参数, 回传一个仅包含该元素的无限 List. 它的递归实现简单的很, 看:</p>
<pre class="code">repeat' :: a -&gt; [a]  
repeat' x = x:repeat' x</pre>
<p>调用 <code>repeat 3</code> 会得到一个以 3 为头部并无限数量的 3 为尾部的 List, 可以说 <code>repeat 3</code> 运行起来就是 <code>3:repeat 3</code> , 然后 <code>3:3:3:3</code> 等等. 若执行 <code>repeat 3</code>, 那它的运算永远都不会停止。而 <code>take 5 (repeat 3)</code> 就可以得到 5 个 3, 与 <code>replicate 5 3</code> 差不多.</p>

<p><code>zip</code> 取两个 List 作参数并将其捆在一起。<code>zip [1,2,3] [2,3]</code> 回传 <code>[(1,2),(2,3)]</code>, 它会把较长的 List 从中间断开, 以匹配较短的 List. 用 <code>zip</code> 处理一个 List 与空 List 又会怎样? 嗯, 会得一个空 List, 这便是我们的限制条件, 由于 <code>zip</code> 取两个参数, 所以要有两个边缘条件</p>
<pre class="code">zip' :: [a] -&gt; [b] -&gt; [(a,b)]  
zip' _ [] = []  
zip' [] _ = []  
zip' (x:xs) (y:ys) = (x,y):zip' xs ys</pre>
<p>前两个模式表示两个 List 中若存在空 List, 则回传空 List. 第三个模式表示将两个 List 捆绑的行为, 即将其头部配对并后跟捆绑的尾部. 用 <code>zip</code> 处理 <code>[1,2,3]</code> 与 <code>['a','b']</code> 的话, 就会在 <code>[3]</code> 与 <code>[]</code> 时触及边界条件, 得到 <code>(1,'a'):(2,'b'):[]</code> 的结果,与 <code>[(1,'a'),(2,'b')]</code> 等价.</p>

<p>再实现一个标准库函数 -- <code>elem</code>! 它取一个元素与一个 List 作参数, 并检测该元素是否包含于此 List. 而边缘条件就与大多数情况相同, 空 List. 大家都知道空 List 中不包含任何元素, 便不必再做任何判断</p>
<pre class="code">elem' :: (Eq a) =&gt; a -&gt; [a] -&gt; Bool  
elem' a [] = False  
elem' a (x:xs)  
    | a == x    = True  
    | otherwise = a `elem'` xs</pre>
<p>这很简单明了。若头部不是该元素, 就检测尾部, 若为空 List 就回传 <code>False</code>.</p>
<a name=""快速"排序"></a><h2>"快速"排序</h2>

<img src="../img/quickman.png" alt="" style="float:right" class="floatright" />
<p>假定我们有一个可排序的 List, 其中元素的类型为 Ord Typeclass 的成员. 现在我们要给它排序! 有个排序算法非常的酷, 就是快速排序 (quick sort), 睿智的排序方法. 尽管它在命令式语言中也不过 10 行, 但在 Haskell 下边要更短, 更漂亮, 俨然已经成了 Haskell 的招牌了. 嗯, 我们在这里也实现一下. 或许会显得很俗气, 因为每个人都用它来展示 Haskell 究竟有多优雅!</p>

<p>它的类型声明应为 <code>quicksort :: (Ord a) =&gt; [a] -&gt; [a]</code>, 没啥奇怪的. 边界条件呢? 如料，空 List。排过序的空 List 还是空 List。接下来便是算法的定义：<b>排过序的 List 就是令所有小于等于头部的元素在先(它们已经排过了序), 后跟大于头部的元素(它们同样已经拍过了序)</b>。 注意定义中有两次排序，所以就得递归两次！同时也需要注意算法定义的动词为"是"什么而非"做"这个, "做"那个, 再"做"那个...这便是函数式编程之美！如何才能从 List 中取得比头部小的那些元素呢？List Comprehension。好，动手写出这个函数！</p>
<pre class="code">quicksort :: (Ord a) =&gt; [a] -&gt; [a]  
quicksort [] = []  
quicksort (x:xs) =  
  let smallerSorted = quicksort [a | a &lt;- xs, a &lt;= x] 
      biggerSorted = quicksort [a | a &lt;- xs, a &gt; x]  
  in smallerSorted ++ [x] ++ biggerSorted</pre>
<p>小小的测试一下, 看看结果是否正确~</p>
<pre class="code">ghci&gt; quicksort [10,2,5,3,1,6,7,4,2,3,4,8,9]  
[1,2,2,3,3,4,4,5,6,7,8,9,10]  
ghci&gt; quicksort "the quick brown fox jumps over the lazy dog"  
" abcdeeefghhijklmnoooopqrrsttuuvwxyz"</pre>
<p>booyah! 如我所说的一样! 若给 <code>[5,1,9,4,6,7,3]</code> 排序，这个算法就会取出它的头部，即 5。 将其置于分别比它大和比它小的两个 List 中间，得 <code>[1,4,3] ++ [5] ++ [9,6,7]</code>, 我们便知道了当排序结束之时，5会在第四位，因为有3个数比它小每，也有三个数比它大。好的，接着排 <code>[1,4,3]</code> 与 <code>[9,6,7]</code>, 结果就出来了！对它们的排序也是使用同样的函数，将它们分成许多小块，最终到达临界条件，即空 List 经排序依然为空，有个插图：</p>

<p>橙色的部分表示已定位并不再移动的元素。从左到右看，便是一个排过序的 List。在这里我们将所有元素与 <code>head</code> 作比较，而实际上就快速排序算法而言，选择任意元素都是可以的。被选择的元素就被称作锚 （<code>pivot</code>），以方便模式匹配。小于锚的元素都在浅绿的部分，大于锚都在深绿部分，这个黄黄的坡就表示了快速排序的执行方式：</p>
<img src="../img/quicksort.png" alt="" style="float:none" class="floatnone" /><a name="用递归来思考"></a><h2>用递归来思考</h2>


<p>我们已经写了不少递归了，也许你已经发觉了其中的固定模式：先定义一个边界条件，再定义个函数，让它从一堆元素中取一个并做点事情后，把余下的元素重新交给这个函数。 这一模式对 List、Tree 等数据结构都是适用的。例如，<code>sum</code> 函数就是一个 List 头部与其尾部的 <code>sum</code> 的和。一个 List 的积便是该 List 的头与其尾部的积相乘的积，一个 List 的长度就是 1 与其尾部长度的和. 等等</p>
<img src="../img/brain.png" alt="" style="float:right" class="floatright" />
<p>再者就是边界条件。一般而言，边界条件就是为避免进程出错而设置的保护措施，处理 List 时的边界条件大部分都是空 List，而处理 Tree 时的边界条件就是没有子元素的节点。</p>

<p>处理数字时也与之相似。函数一般都得接受一个值并修改它。早些时候我们编写过一个计算 Fibonacci 的函数，它便是某数与它减一的 Fibonacci 数的积。让它乘以零就不行了， Fibonacci 数又都是非负数，边界条件便可以定为 1，即乘法的单比特。 因为任何数乘以 1 的结果还是这个数。而在 <code>sum</code> 中，加法的单比特就是 0。在快速排序中，边界条件和单比特都是空 List，因为任一 List 与空 List 相加的结果依然是原 List。</p>

<p>使用递归来解决问题时应当先考虑递归会在什么样的条件下不可用, 然后再找出它的边界条件和单比特, 考虑参数应该在何时切开(如对 List 使用模式匹配), 以及在何处执行递归.</p>

            <ul class="nav">
                <li class="left">  <img src="../img/prv.png" alt="prev" /><a href="syntax-on-function.html">函数的语法</a></li>
                <li class="center"><a href="chapters.html">目录</a></li>
                <li class="right"> <a href="high-order-function.html">高阶函数</a><img src="../img/nxt.png" alt="next" /></li>
            </ul>
        </div>
        <div id="footer">
        </div>
        <div id="feedback">Send feedback</div>
    </body>
</html>
